package com.fantaike.algorithm.linear;

import java.util.Arrays;
import java.util.Iterator;

/**
 * 顺序表：是在计算机内存中以数组的形式保存的线性表，线性表的顺序存储是指用一组地址连续的存储单元，依次存
 * 储线性表中的各个元素、使得线性表中再逻辑结构上响铃的数据元素存储在相邻的物理存储单元中，即通过数据元
 * 素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。
 * @author jishushen
 * @date  2021-08-21 9:37
 */
@SuppressWarnings("unchecked")
public class SequenceList<T> implements Iterable<T>{

    //存储元素的数组
    private T[] eles;
    //当前顺序表中元素的个数,个数减一就是最大索引
    private int N;


    //创建容量为capacity的SequenceList对象
    public SequenceList(int capacity){
        //构造方法创建一个数组
        this.eles = (T[]) new Object[capacity];
        //初始数组的元素个数为0
        this.N = 0;
    }

    //空置线性表
    public void clear(){
        this.N = 0;
    }

    //判断线性表是否为空，是返回true，否返回false
    public boolean isEmpty(){
        return N == 0;
    }
    //获取线性表中元素的个数
    public int length(){
        return N;
    }

    //读取并返回线性表中的第i个元素的值
    public T get(int i){
        return eles[i];
    }

    //在线性表的第i个元素之前插入一个值为t的数据元素。
    public void insert(int i,T t){
        if (N == eles.length){
            reSize(2 * eles.length);
        }
        //在i处插入一个元素，就说在i以后的元素都要向后移一位,所以倒叙遍历，将前一个数赋值到他后一个数的位置
        if (N - i >= 0) System.arraycopy(eles, i, eles, i + 1, N - i);
        eles[i] = t;
        N++;
    }

    //向线性表中添加一个元素t
    public void insert(T t){
        if (N == eles.length){
            reSize(2 * eles.length);
        }
        eles[N++] = t;
    }

    //删除并返回线性表中第i个数据元素。
    public T remove(int i){
        if(i<0 || i>N-1){
            throw new RuntimeException("当前要删除的元素不存在");
        }
        //删除i处的数据就说明，i后面的数据要向前移动
        //首先获取i处的值
        T current = eles[i];
        //将数据向前移动
        for (int index = i; index < N - 1; index++) {
            eles[i] = eles[i+1];
        }
        N--;

        //缩容
        if (N < eles.length/4){
            reSize(eles.length / 2);
        }

        return current;
    }

    //扩容或者缩容
    private void reSize(int newSize){
        eles = Arrays.copyOf(eles, newSize);
    }

    //返回线性表中首次出现的指定的数据元素的位序号，若不存在，则返回-1
    public int indexOf(T t){
        if(t == null){
            throw new RuntimeException("查找的元素不合法");
        }
        for (int i = 0; i < N; i++) {
            if (t.equals(eles[i])){
                return i;
            }
        }
        return -1;
    }

    /**
     * 让SequenceList实现Iterable接口，重写iterator方法；
     * @Date: 2021/8/21 12:28
     * @Author: xuepeng
     * @Return
     * @Throws
     */
    @Override
    public Iterator<T> iterator() {
        return new SIterator();
    }

    /**
     * 在java中，遍历集合的方式一般都是用的是foreach循环，如果想让我们的SequenceList也能支持foreach循环，
     * 则需要做如下操作：
     *  1.让SequenceList实现Iterable接口，重写iterator方法；
     *  2.在SequenceList内部提供一个内部类SIterator,实现Iterator接口，重写hasNext方法和next方法；
     * @className: SequenceList
     * @Author: xuepeng
     * @Date: 2021/8/21 12:25
     * @version: v1.0 文件初始创建
     */
    private class SIterator implements Iterator<T>{
        private int cusor;
        public SIterator(){
            this.cusor = 0;
        }
        @Override
        public boolean hasNext() {
            return cusor < N;
        }

        @Override
        public T next() {
            return eles[cusor++];
        }
    }
}
